package com.wang.fuxi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

public class DataStructure {

	public static void main(String[] args) {
		/**
		 * 集合框架：
			Iterable（迭代器接口，实现了该接口可以使用foreach,还可以获取集合对象的迭代器对象，通过迭代器遍历集合） 
				|
				|---iterator() =======>Iterator
				|					  		|	
				|	listIterator()获取	ListIterator
				|
		 * 	Collection(所有集合的根接口)  
		 * 		|----List(接口)表示有序（存入和取出）可重复集合，可以保存null元素 
		 * 				|---ArrayList(实现类) 基于数组，查改快  
		 * 				|---LinkedList(实现类)基于变量，增删快 
		 * 				|	因为LinkedList中有多个接口的实现方法，所以，同样一个功能可以有多个方法实现，
		 * 					但是，尽量不要交叉使用（使用同一个接口中的方法），因为交叉使用就会导致
		 *					既不能完全具其中有一个接口的完整特性
		 * 				|---Vector(就是一个线程安全的ArrayList) 
		 * 
		 * 		|----Set(接口)表示无序（存入和取出）不可重复集合，可以保存null元素
		 * 				|----HashSet(实现类)：基于HashMap，HashMap基于HashCode，是一个非线程安全。
		 * 						判断重复的机制：
		 * 							1. 先判断元素的hashCode值
		 * 							2. 在hashCode相等的情况下，继续判断equals比较，如果都相等认为是同一个元素
		 * 
		 * 				|----TreeSet(实现类)：基于TreeMap，TreeMap底层基于红黑树（特殊的二叉树，左边叉值小，右边叉值大）
		 * 				|		1. 自然排序：元素类型必须实现了Comparable接口，且必须重写compareTo（）方法
									返回值  正数：升序
								           返回值 负数：降序
									返回值0：相同的元素
									
								2. 定制排序：
		 * 							在创建TreeSet对象的时候，传入一个Comparator接口的实现类，该实现类必须重写compare方法
		 * 							返回值  正数：升序
								           返回值  负数：降序
									返回值 0：相同的元素
		 * 					当自然排序和定制排序同时使用，定制排序优先级更高
		 * 				|
		 * 				|----LinkedHashSet(是一个有序的HashSet，在HashSet基础上维护了一个链表) 
		 * 
		 * 		|-----Queue队列 
		 * 				|---Deque双端队列
		 * 			 	|---Stack栈
		 * 
		 * 
		 * 	集合遍历方式：		只有List才有双向迭代器
		 * 
		 *		1. foreach()因为ArrayList间接实现了Iterable接口
		 *		2. 迭代器：一个集合对象可以获取多个迭代器对象（多次调用方法）,指针都是在初始位置（第一个元素前面）
		 *			Iterator<E> iterator()  单向迭代器
		 *				1. boolean hasNext() 如果迭代具有更多元素，则返回 true 。  
						2. Object next() 返回迭代中的下一个元素。  
						3. default void remove() 从底层集合中删除此迭代器返回的最后一个元素（可选操作）。 
					
					ListIterator<E> listIterator() 双向迭代器
						void add(E e) 
							将指定的元素插入列表（可选操作）。  
						boolean hasNext() 
							返回 true如果遍历正向列表，列表迭代器有多个元素。  
						boolean hasPrevious() 
							返回 true如果遍历反向列表，列表迭代器有多个元素。  
						E next() 
							返回列表中的下一个元素，并且前进光标位置。  
						int nextIndex() 
							返回随后调用 next()返回的元素的索引。  
						E previous() 
							返回列表中的上一个元素，并向后移动光标位置。  
						int previousIndex() 
							返回由后续调用 previous()返回的元素的索引。  
						void remove() 
							从列表中删除由 next()或 previous()返回的最后一个元素（可选操作）。  
						void set(E e) 
							用 指定的元素替换由 next()或 previous()返回的最后一个元素（可选操作）。  

		 *		3.遍历集合方式3：通过普通for循环，利用集合size()方法和get(int index)	（不常用）
		 *
		 * 		注意：在使用迭代器遍历集合的时候，不能使用集合自己的方法（增删改）操作集合对象
		 */
		ArrayList list1 = new ArrayList();
		// 1.static boolean addAll(Collection c,Object...elements)将所有指定的元素添加到指定的集合。
		Collections.addAll(list1,1,2,43,69);
		System.out.println(list1);//[1, 2, 43, 69]
		/*
		 * 查询集合中是否有一个指定的元素，查到返回元素，查不到返回null
		 */
		// 3.static List emptyList() 返回空列表
		// 作为一种状态使用就跟-1,有时候用null不能正确的表示这种状态的时候用
		List<Object> emptyList = Collections.emptyList();
		System.out.println(emptyList);//[]类比 -1,一般用来表示一种状态
		// 4.static Map<K,V> emptyMap()
		// 作为一种状态使用就跟-1,有时候用null不能正确的表示这种状态的时候用
		// 5.static Set<T> emptySet()
		// 6.static void fill(List list1, Object obj)用指定的元素代替指定列表的所有元素。
//		Collections.fill(list1, "防狼喷雾");
//		System.out.println(list1);
		// 7.static Object max(Collection coll)根据其元素的自然顺序返回给定集合的最大元素。
//		Object max = Collections.max(list1);//必须是满足自然排序要求
		// 8.static Object max(Collection coll, Comparator  comp)根据定制排序返回给定集合的最大元素。
		// 9.static Object min(Collection coll)根据其元素的自然顺序返回给定集合的最小元素。
		// 10.static Object min(Collection coll, Comparator comp)据定制排序返回给定集合的最小元素。
		// 11.static void reverse(List list1)反转指定列表中元素的顺序。
		Collections.reverse(list1);
		System.out.println(list1); //[69, 43, 2, 1]
		// 12.static void shuffle(List list1)常常用来洗牌，打乱集合中元素的排序
		Collections.shuffle(list1);
		System.out.println(list1);//[1, 69, 43, 2]
		// 16.static void sort(List list1) 根据其元素自然排序。
		Collections.sort(list1);
		System.out.println(list1);//[1, 2, 43, 69]
		// 17.static void sort(List list1, Comparator c)根据指定的比较器引起的顺序对指定的列表进行排序。
		// 18.static void swap(List list1, int i, int j)交换下标i和下标j的元素位置。
		Collections.swap(list1,0,3);
		System.out.println(list1);//[69, 2, 43, 1]
		// 19.static List synchronizedList(List list1)将list1对象转换为线程安全的。
		// 20.static Map<K,V> synchronizedMap(Map<K,V> m)将map对象转换为线程安全的。
		// 21.static Set<T> synchronizedSet(Set s)将set对象转换为线程安全的。
		/*
		 * 构造方法：
		 * 		1. ArrayList() 构造一个初始容量为十的空列表。  
				2. ArrayList(Collection c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。  
				3. ArrayList(int initialCapacity) 构造具有指定初始容量的空列表。  
		 */
		ArrayList list = new ArrayList();
		// 1.boolean add(E e)将指定的元素追加到此列表的末尾。如果添加的是其他集合，则会将其他集合作为整体插入
		list.add(1);
		list.add(3.14);
		list.add(true);
		list.add("波波");
		list.add("黄鳝");
		list.add(new int[3]);
		System.out.println(list);
		// 2.void add(int index, Object element)在此列表中的指定位置插入指定的元素。
		list.add(4,"狼牙棒");
		System.out.println(list);
		// 3.boolean addAll(Collection c)按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
		ArrayList tools = new ArrayList();
		tools.add("皮鞭");
		tools.add("皮大衣");
		tools.add("黑皮鞋");
		tools.add("皮鞭");
		tools.add("手铐");
		tools.add("蜡烛");
		list.addAll(tools);//会将集合中元素插入，而不是将集合作为整体插入
//		list.add(tools);//会将集合作为整体插入
		System.out.println(list);
		// 4.void clear() 从列表中删除所有元素。
//		list.clear();
//		System.out.println(list);
		// 5.boolean contains(Object o) 判定当前集合中是否包含 o这个元素
		boolean contains = list.contains("眼罩");
		System.out.println(contains);
		// 6.E get(int index)返回此列表中指定位置的元素。
		Object object = list.get(2);
		System.out.println(object);
		// 7.int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。
		int indexOf = list.indexOf("蜡烛");
		System.out.println(indexOf);
		// 8.int lastIndexOf(Object o) 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
		int lastIndexOf = list.lastIndexOf("皮鞭");
		System.out.println(lastIndexOf);
		// 9.boolean isEmpty()如果此列表不包含元素，则返回 true 。
		System.out.println(list.isEmpty());
		// 10.E remove(int index) 删除该列表中指定位置的元素。
		Object remove = list.remove(10);
		System.out.println(remove);
		System.out.println(list);
		// 11.boolean remove(Object o) 从列表中删除指定元素的第一个出现（如果存在）。注意：如果传入的参数是int类型，会默认调用下标的删除方法，如果想要删除的是Integer元素，则必须制定参数是Integer类型
		boolean remove2 = list.remove(Integer.valueOf(1));//需要删除1这个元素，这里就必须用包装类手动包装一下
		System.out.println(remove2);
		System.out.println(list);
		// 12.boolean removeAll(Collection c)从此列表中删除指定集合中包含的所有元素。
		System.out.println(tools);
		boolean remove3 = list.removeAll(tools);
		System.out.println(remove3);
		System.out.println(list);
		// 13.E set(int index, E element)将指定下标index处的元素修改为element
		list.set(0, "钱包");
		System.out.println(list);
		// 14.int size() 返回此列表中的元素数。
		System.out.println(list.size());
		// 15.Object[] toArray()将ArrayList对象转换为数组	重要
		Object[] array = list.toArray();
		System.out.println(Arrays.toString(array));
		Character[] arr = {'a','b'};
		//扩展：将数组转换为集合对象	static <T> List<T> asList(T... a) 返回由指定数组支持的固定大小的列表。  注意：这里必须是包装类的数组才能转换为集合对象
		List<Character> asList = Arrays.asList(arr);//数组是什么类型，集合中元素就全是这个类型的
		List<Object> asList2 = Arrays.asList(array);//数组是什么类型，集合中元素就全是这个类型的
		// 16.void trimToSize() 将ArrayList对象中未使用的空间去除（基本不用）
	//以下方法自己练习
		//boolean add(E e) 将指定的元素追加到此列表的末尾。  
		//void add(int index, E element) 在此列表中的指定位置插入指定的元素。  
		//boolean addAll(Collection<? extends E> c) 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。  
		//boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到此列表中，从指定的位置开始。  
		//void addFirst(E e) 在该列表开头插入指定的元素。  
		//void addLast(E e) 将指定的元素追加到此列表的末尾。  
		//void clear() 从列表中删除所有元素。  
		//boolean contains(Object o) 如果此列表包含指定的元素，则返回 true 。  
		//E element() 检索但不删除此列表的头（第一个元素）。  
		//E get(int index) 返回此列表中指定位置的元素。  
		//E getFirst() 返回此列表中的第一个元素。  
		//E getLast() 返回此列表中的最后一个元素。  
		//int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。  
		//int lastIndexOf(Object o) 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。  
		//ListIterator<E> listIterator(int index) 从列表中的指定位置开始，返回此列表中元素的列表迭代器（按适当的顺序）。  
		//boolean offer(E e) 将指定的元素添加为此列表的尾部（最后一个元素）。  
		//boolean offerFirst(E e) 在此列表的前面插入指定的元素。  
		//boolean offerLast(E e) 在该列表的末尾插入指定的元素。  
		//E peek() 检索但不删除此列表的头（第一个元素）。  
		//E peekFirst() 检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。  
		//E peekLast() 检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。  
		//E poll() 检索并删除此列表的头（第一个元素）。  
		//E pollFirst()检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。  
		//E pollLast()检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。  
		//E remove() 检索并删除此列表的头（第一个元素）。  
		//E remove(int index) 删除该列表中指定位置的元素。  
		//boolean remove(Object o) 从列表中删除指定元素的第一个出现（如果存在）。  
		//E removeFirst() 从此列表中删除并返回第一个元素。  
		//
		//E removeLast() 从此列表中删除并返回最后一个元素。  
		//
		//E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。  
		//int size()  返回此列表中的元素数。
		//
		//Object[] toArray()  将集合对象转换为数组
		/*
		 * 构造方法：
		 * 		1. HashSet() 
					构造一个新的空集合; 具有默认初始容量（16）和负载因子（0.75）。  
				2. HashSet(Collection c) 
					构造一个包含指定集合中的元素的新集合。  
				3. HashSet(int initialCapacity) 
					创建一个新的空集合; 可以指定的初始容量initialCapacity和默认负载因子（0.75：扩容机制，当达到75%容量就扩容）。  
				4. HashSet(int initialCapacity, float loadFactor)  就是用默认的，经过测试效率和空间比是最高的
					创建一个指定容量和加载因子的空集合对象
		 */
		HashSet set = new HashSet();
		set.add(1);
		set.add(1);
		set.add("小姨子");
		set.add("小姨子");
		set.add("隔壁老王");
		set.add("隔壁老王");
		set.add("五姑娘");
		set.add("五姑娘");
		System.out.println(set);
		System.out.println("=============添加自定义类型===========");
		//需求：认为姓名和电话号都相等是同一个对象。		测试判断HashSet判断重复的机制
		Student stu1 = new Student("苍苍","6969669");
		Student stu2 = new Student("苍苍","6969669");
		System.out.println("stu1.hashCode() = " + stu1.hashCode());
		System.out.println("stu2.hashCode() = " + stu2.hashCode());
		System.out.println(stu1.equals(stu2));
		set.add(stu1);
		set.add(stu2);
		System.out.println(set);
		//剩余方法和遍历和List一样，只是Set没有双向迭代器
		/*
		 * 构造方法：
		 * 		TreeSet() 构造一个新的，空的树组，根据其元素的自然排序进行排序。  
				TreeSet(Collection c) 构造一个包含指定集合中的元素的新树集，根据其元素的 自然排序进行排序 。  
				TreeSet(Comparator comparator) 构造一个新的，空的树集，根据指定的比较器进行排序。  
					可以使用Comparator的实现类对象
					也可以使用Comparator的匿名内部类
		 */
		//创建一个User类型元素的比较器对象
		UserComparator comparator = new UserComparator();
		//将对象传入TreeSet构造方法中，定制排序
//		TreeSet set = new TreeSet(comparator);
		//使用匿名内部类方式：
		TreeSet set1 = new TreeSet(new Comparator<User>() {
			@Override
			public int compare(User o1, User o2) {
				return 0;//自己写业务判断
			}
		});
		System.out.println("=============添加自定义类型===========");
		//测试判断TreeSet判断重复的机制:定制排序 
		//自然排序：使用无参构造创建TreeSet对象，要添加的元素必须实现Comparable接口，重写compareTo()方法 
		//需求：学生类，姓名长度升序，如果姓名长度相同，再根据身高升序排序，如果姓名长度和身高长度都相等，则认为同一个元素		主要看：compareTo方法返回值
		set1.clear();
		User stu11 = new User("苍苍",160);
		User stu21 = new User("苍苍",160);
		User stu8 = new User("翔翔",160);
		User stu3 = new User("翔翔有点短",170);
		User stu4 = new User("翔翔有点短",169);
		User stu5 = new User("张某民有点小",196);
		User stu6 = new User("张某民有点小很小",196);
		User stu7 = new User("张某民有点小是很小非常小",169);
		set1.add(stu11);
		set1.add(stu21);//因为根据元素的姓名长度和身高比较判断是否重复，所以不会添加该元素，因为前面有stu1苍苍了
		set1.add(stu3);
		set1.add(stu4);
		set1.add(stu5);
		set1.add(stu6);
		set1.add(stu7);
		set1.add(stu8);//因为根据元素的姓名长度和身高比较判断是否重复，所以不会添加该元素，因为前面有stu1苍苍了
		System.out.println(set1);
		TreeSet treeSet = new TreeSet();
		treeSet.add(0);
		treeSet.add(1);
		treeSet.add(2);
		treeSet.add(3);
		treeSet.add(5);
		treeSet.add(6);
		//E ceiling(E e) 返回此集合中大于或等于给定元素的最小元素，如果没有此元素，则返回 null 。 
		Object ceiling = treeSet.ceiling(4);//集合中没有4
		System.out.println(ceiling);//
		//E floor(E e) //返回此集合中小于或等于给定元素的最大的元素，如果没有这样的元素，则返回 null 。 
		Object floor = treeSet.floor(4);//集合中没有4
		System.out.println(floor);//
		//E first() //返回此集合中当前的第一个（最低）元素。  
		Object first = treeSet.first();//
		System.out.println(first);//
		//E last() 
		//返回此集合中当前的最后（最高）元素。  
		//Iterator<E> iterator() 
		//以升序返回该集合中的元素的迭代器。  
		//E lower(E e) 返回这个集合中最大的元素严格小于给定的元素，如果没有这样的元素，则返回 null 。  
		Object lower = treeSet.lower(0);//
		System.out.println(lower);//
		//E pollFirst() 
//		treeSet.clear();
		Object pollFirst = treeSet.pollFirst();//检索并删除第一个（最低）元素，或返回 null如果该集合为空。  
		System.out.println(pollFirst);//
		//E pollLast() 
		//检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 。  
	}

}
class Student{
	private String name;
	private String cellPhone;
	public Student() {
	}
	public Student(String name, String cellPhone) {
		super();
		this.name = name;
		this.cellPhone = cellPhone;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String getCellPhone() {
		return cellPhone;
	}
	public void setCellPhone(String cellPhone) {
		this.cellPhone = cellPhone;
	}
	@Override
	public String toString() {
		return "[" + name + ", " + cellPhone + "]";
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((cellPhone == null) ? 0 : cellPhone.hashCode());
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Student other = (Student) obj;
		if (cellPhone == null) {
			if (other.cellPhone != null)
				return false;
		} else if (!cellPhone.equals(other.cellPhone))
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}
	
}
class User implements Comparable<User>{
	private String name;
	private double height;
	public User() {
	}
	public User(String name, double height) {
		super();
		this.name = name;
		this.height = height;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public double getHeight() {
		return height;
	}
	public void setHeight(double height) {
		this.height = height;
	}
	@Override
	public String toString() {
		return "[" + name + ", " + height + "]";
	}
	@Override
	public int compareTo(User o) {
		//需求：学生类，姓名长度升序，如果姓名长度相同，再根据身高升序排序，如果姓名长度和身高长度都相等，则认为同一个元素	
		if (this.name.length() > o.name.length()) {
			return 1;//正数表示升序
		} else if (this.name.length() < o.name.length()){
			return -1;//负数表示降序
		} else {//表示姓名长度相等才会进else
			if (this.height > o.height) { //姓名长度相等,按身高升序
				return 1;//正数表示升序
			} else if (this.height < o.height){//姓名长度相等,按身高降序
				return -1;//负数表示降序
			} else {//表示姓名长度相等且身高也相等才会进else
				return 0;//表示相同的元素
			}
		}
	}
	
}